class Node {
    constructor(data) {
        this.element = data
        this.next = null
    }
}

module.exports = class LinkedList {
    /**
     * 头结点
     */
    #head = null
    /**
     * 链表长度
     */
    #count = 0

    /**
     * 向链表尾部添加元素
     * @param {any} data 
     * @returns {Node} node
     */
    push(data) {
        // 1.创建node节点并放入数据
        const node = new Node(data)
        // 2.如果当前头节点为空，将该节点作为头结点。
        if (this.#head === null) {
            this.#head = node
            this.#count++
            return
        }
        // 3.寻找到当前队列最后一个节点
        const lastNode = this.getNodeByIndex(this.#count - 1)
        // 4.将该节点拼接至当前最后一个节点的后面
        lastNode.next = node
        // 5.链表长度 +1
        this.#count++
        return node
    }

    /**
     * 根据索引删除指定节点
     * @param {*} index 
     * @returns {Node} removed node
     */
    removeNodeByIndex(index) {
        // 1.如果输入索引对应元素不存在，直接返回
        if (index < 0 || index > this.#count) return;
        // 2.如果删除的是头结点，将原头结点的下一个节点作为头结点
        if (index === 0) {
            const currentNode = this.#head
            this.#head = this.#head.next
            this.#count --
            return currentNode
        }
        // 3.如果索引对应元素存在，先找到预删除节点的前一个节点
        const preNode = this.getNodeByIndex(index - 1)
        const currentNode = preNode.next
        // 4.获取预删除节点的后一个节点
        const nextNode = preNode.next.next
        // 5.将预删除节点的前一个节点的 next 指向预删除节点的后一个节点
        preNode.next = nextNode
        // 6.链表长度 -1 
        this.#count--
        return currentNode
    }

    /**
     * 根据输入数据删除对应链表上第一次出现该数据的节点
     * @param {any} data 
     * @returns removed node
     */
    removeNodeByData(data) {
        return this.removeNodeByIndex(this.indexOf(data))
    }

    /**
     * 指定位置插入节点
     * @param {any} data 
     * @param {number} index 
     * @returns true | false
     */
    insert(data, index) {
        // 1.如果插入范围越界，直接返回 false
        if (index > this.#count || index < 0) return false;
        // 2.初始化待插入节点
        const node = new Node(data)
        // 3.如果插入链表头，建原表头连接至节点后面，再将新节点设置成链表头
        if (index === 0) {
            node.next = this.#head
            this.#head = node
            this.#count++
            return true
        }

        // 4.如果插入链表中间，先找到插入位置的前一个元素，将前一个节点的 next 指向插入节点，将插入节点的 next 指向原位置元素
        const preNode = this.getNodeByIndex(index - 1)
        node.next = preNode.next
        preNode.next = node
        this.#count++
        return true
    }

    /**
     * 查找出链表中第一个出现输入数据的链表节点的索引
     * @param {any} data 
     * @returns number
     */
    indexOf(data) {
        for (let i = 0; i < this.#count; i++) {
            if (this.#equalWith(data, this.getNodeByIndex(i).element)) {
                return i
            }
        }
        return -1
    }

    /**
     * 根据索引查找指定节点
     * @param {string | number} index 
     * @returns {Node} node
     */
    getNodeByIndex(index) {
        // 如果输入索引对应元素不存在，直接返回
        if (index < 0 || index >= this.#count) return;
        let result = this.#head
        for (let i = 0; i < index; i++) {
            result = result.next
        }
        return result
    }

    /**
     * 获取链表长度
     * @returns 链表长度
     */
    size() {
        return this.#count
    }

    /**
     * 是否为空链表
     * @returns true | false
     */
    isEmpty(){
        return this.#count === 0
    }

    /**
     * 工具方法，比较输入是否相同
     * @param {any} a 
     * @param {any} b 
     * @returns true | false
     */
    #equalWith(a, b) {
        return JSON.stringify(a) === JSON.stringify(b)
    }
    /**
     * 打印链表
     */
    printList() {
        for (let i = 0; i < this.#count; i++) {
            console.log(this.getNodeByIndex(i));
        }
    }

}